Calculations on computer systems involving the locations of objects situated on, or referenced to, the surface of the earth require a location coding system, a particular computer representation of geospatial location. Depending on the application, a location code may represent a zero-dimensional point, a one-dimensional line/curve, or a two-dimensional region, or a set of these location forms. A location coding must define a quantization operator which maps such locations on the earth's surface to location codes, which consist of a string of bits on modern digital computers.
As defined in (Sahr, K., D. White, and A. J. Kimerling. 2003. “Geodesic Discrete Global Grid Systems”, Cartography and Geographic Information Science. 30(2):121-134), the contents of which are incorporated herein by reference, a discrete global grid (DGG) is a set of polygonal regions that partition the surface of the earth, where each region has associated with it a single point contained within it (usually the region center point). Each region/point pair is designated a cell. A discrete global grid system (DGGS) is a multi-resolution set of discrete global grids.
DGGS have been developed using multi-resolution aperture 3 hexagon grids tiled onto an icosahedron. These DGGS include the ISEA3H DGGS as defined in (Sahr, K., D. White, and A. J. Kimerling. 2003. “Geodesic Discrete Global Grid Systems”, Cartography and Geographic Information Science. 30(2):121-134), the contents of which are incorporated herein by reference. The cells of a hexagon-based icosahedral DGGS always include exactly twelve pentagonal cells at each resolution; these are located at the twelve vertices of the icosahedron.
The cells of any DGGS can have at least three relationships to the geospatial locations being represented:
1. Vector systems (Dutton, G. 1989. “The fallacy of coordinates”, Multiple representations: Scientific report for the specialist meeting. Santa Barbara, National Center for Geographic Information and Analysis). For each resolution in a DGGS, each point on the earth's surface is mapped to the DGG cell point associated with the DGG cell region in which it occurs. Line/Curves can be represented as an ordered vector of cell point vertexes. A region can be represented using a line/curve representation of it's boundary.
2. Raster systems. The areal units associated with the cells of the DGGS form the pixels of a raster system. For each resolution in a DGGS, each point on the earth's surface is mapped to the DGG cell region in which it occurs. Line/Curves can be represented as an ordered vector of cell regions intersected by the curve. A region can be represented using a line/curve representation of it's boundary, or as the set of pixels containing, intersecting, or contained by the location being represented.
3. Bucket systems. The areal regions associated with the DGGS cells are buckets into which data objects are assigned based on their location. Depending on the application, a data object can either be assigned to the finest resolution cell which entirely contains it, or to the coarsest resolution cell which uniquely distinguishes it from all other data objects in the data set of interest.
In order to be useful on a computer system each cell in a DGGS has assigned to it one or more unique location codes, each of which is an address consisting of a string of bits on the computing system. These location codes generally take one of two forms:
1. Pyramid Address (as outlined in Burt, P J, 1980, “Tree and Pyramid Structures for Coding Hexagonally Sampled Binary Images”, Computer Graphics and Image Processing, 14:271-280). Each cell is assigned a unique location code within the DGG of corresponding resolution. This single-resolution location code may be multi-dimensional or linear. Given a resolution K cell with single-resolution location code K-add, we can designate the DGGS pyramid location code to be the pair (K, K-add). A multi-resolution DGGS address representation of a location can be constructed by taking the series of single-resolution DGG addresses ordered by increasing resolution.
Pyramid addresses are useful in applications that make use of single resolution data sets. Quantization operators to/from pyramid addresses are known for grids based on triangles, squares, diamonds, and hexagons.
2. Path Address. The resolution K quantization of a geospatial location into a DGGS cell restricts the possible resolution K+1 quantization cells to those whose regions overlap or are contained within the resolution K cell. We can construct a spatial hierarchy by designating that each resolution K cell has as children all K+1 cells whose regions overlap or are contained within it's region. A path address is one which specifies the path through a spatial hierarchy that corresponds to a multi-resolution location quantization. Path addresses are often linear, with each digit corresponding to a single resolution and specifying a particular child cell of the parent cell specified by the address prefix.
The reduction in redundant location information allows path addresses to be smaller than pyramid addresses. And because the number of digits in a location code corresponds to the maximum resolution, or precision, of the address, path addresses automatically encode their precision (Dutton, G. 1989. “The fallacy of coordinates”, Multiple representations: Scientific report for the specialist meeting. Santa Barbara, National Center for Geographic Information and Analysis).
Path addresses are also used to enable hierarchical algorithms. In particular, the coarser cell represented by the prefix of a location code can be used as a coarse filter for the proximity operations containment, equality, intersection/overlap, adjacency, and metric distance. These proximity operations are the primary forms of spatial queries used in spatial databases, and such queries are thus rendered more efficient by the use of path addresses. For example, take a system where data object boundaries are assigned to the smallest containing bucket cell. A query may ask for all data objects whose locations intersect a particular region. We can immediately discard from consideration all objects in bucket cells that do not intersect the smallest containing bucket cell of the query region (Samet, H. 1989. The Design and Analysis of Spatial Data Structures. Menlo Park, Calif.: Addison-Wesley).
Path addresses are usually associated with spatial hierarchies which form traditional trees, where each child has one and only one parent. Such hierarchies include those created by recursively subdividing square, triangle, or diamond cell polygons. However, the spatial hierarchies formed by aperture 3 hexagon grids do not form trees; each cell can have up to three parents. For this reason aperture 3 hexagon grids have previously been addressed using pyramid addressing systems.